1. Field of the Invention
This invention relates in general to error correction coding, and more particularly, to a trellis encoder/decoder constellation mapping from binary data to symbols and inverse mapping suited to error-correction on a high-speed data channel.
2. Description of Related Art
To minimize the effects of additive white Gaussian noise (AWGN) as well as the effects of Rayleigh fading and other channel impairments, one or more error encoding techniques are used in order to provide for accurate transmission and detection of data, especially when very high level modulation schemes are employed.
Trellis-coded modulation is a forward error correction coding technique which is also well known in the art. Trellis codes are convolutional codes that are designed and optimized according to a specific modulation scheme. A convolutional encoder encodes information symbols based upon the present input symbol and the state of the encoder. The present state of the encoder is determined by the symbols which previously entered the encoder. That is, the encoded symbol is a function of the present input symbol and also symbols that entered the encoder before the present input symbol. Thus, a convolutional encoder has memory.
Convolutional codes are typically implemented by shift registers and summers. The next state and the output of the encoder are functions of the present state of the register or look-up table (i.e., the value of the bits presently stored within the register or look-up table memory), and the input to the register or look-up table.
FIG. 1A and the accompanying table 230 shown in FIG. 1B illustrate an exemplary embodiment of a convolutional encoder 200 implemented by means of shift registers, and the corresponding state table. The encoder 200 is simply shown here in order to illustrate the operation and implementation of convolutional encoder, and is not to be construed as an implementation of the trellis encoder used in accordance with the present invention. The encoder 200 includes shift register memory units 205, 210, 215, as well as summers 220, 225. A one-bit input is encoded into a two-bit output to provide rate xc2xd encoding.
Assuming an initial state of 000 (i.e., the register units 205, 210, 215 contain bit values of 0, 0, 0, respectively), and an input value of 0, the next state of the encoder 200 is 000 (a zero bit value shifts in while a zero value shifts out). Consequently, the value of the two bits at the output is 00. This is represented in the first line of the state table 230 if FIG. 1B. Note, however, that the present and next state columns only indicate two-bit values since the last state bit is always shifted out and is not significant in determining the next state. Thus, when moving from state to state, the encoder 200 can be considered to have four possible present states and four next states, each two-bit values. As another example, assume the encoder 200 to be in the present state 10 (i.e., the first two registers contain 1,0). An input of 1 will move the encoder 200 to the next state of 11 (i.e., the first two registers contain 1,1) and generate an output of 01 (decimal 1). This process is repeated as each successive bit enters the encoder 200 so that a state diagram can be constructed which shows the possible state transitions of the encoder 200 with the accompanying input and output values which correspond to those transitions.
FIG. 2 is a state transition diagram which indicates the possible state transitions of the encoder 200 of FIG. 1, along with the input and output values corresponding to the possible transitions. Because the state transition diagram resembles a trellis in form, such diagrams are often called trellis diagrams, hence the name xe2x80x9ctrellis coding.xe2x80x9d Each dot on the trellis diagram of FIG. 2 represents a state of the encoder 200. Dots in the same horizontal row correspond to the same state at different times. Dots in the same vertical column represent different states at the same time (i.e., within the duration of the same symbol). Branches between the dots represent possible state transition paths. Thus, for example, there is a branch between the state 01 and the state 00 which indicates that, given the appropriate input, the encoder 200 could go from state 01 to state 00. Since there is no branch between states 01 and 11, nor is there a branch between the states 01 and 11, it is possible for the encoder 200 to go from state 01 to either of the states 11 or 01 within one symbol duration.
The number pair along each of the branches depicted in FIG. 2 indicate the [input, output] values which correspond to a given branch. The first number represents the input which causes the transition, while the second number represents the output value resultant upon this transition.
As seen from the trellis diagram of FIG. 2, the possible state transitions for the encoder 200 are the same for each successive symbol. Thus, the same pattern repeats over and over again for each symbol duration.
As an example, assume the encoder 200 begins in the state 0 (binary 00), represented by a dot 300 in FIG. 2. Upon application of an input value 1 to the encoder 200, the encoder 200 goes from state 0 to state 2 (binary 10), represented by a dot 320, via a path 310. Upon completion of the transition, the encoder 200 outputs a value 3 (binary 11). If the value of the next bit applied to the input is 0, the encoder 200 transitions from state 2 to state 1, represented by a dot 340, via a path 330, while the output of the encoder 200 assumes a value of 2. Finally, upon application of input bit of 0, the encoder 200 moves from the state 1 to the state 0, represented by a dot 360, via a path 350. Upon entering the 0, the encoder 200 outputs a value 3. Thus, in the foregoing example, input bits 1-0-1 are encoded by the encoder 200 into output bits 11-10-11, or 3-2-3 in decimal. At the same time, the encoder 200 has transitioned from the state 0 to the state 2, to the state 1, and back to the state 0.
As further explained below, convolutional encoding (and Viterbi decoding) provides for a reduced number of detected errors at the receiver. Consider again the trellis diagram of FIG. 2. For example, assume that a three-bit data stream 1-0-0 is properly encoded as 11-10-11 by the encoder 200 as described above. Also suppose that the receiver detects the transmitted signal erroneously as 11-11-11. In order to determine what the original transmitted data is, the decoder performs a maximum likelihood decision based upon the possible state transition paths which the encoder 200 might have taken. Since the encoder is typically set to state 0 at initialization, the decoder assumes that the detected sequence of data bits began in state 0. The decoder then examines all of the paths which began at state 0 and terminate at a state three symbols later as depicted in FIG. 2 for the purpose of illustration. For instance, for an ending point at the state 0, at the point 360, there are two possible paths which the encoder may have taken: the path 310, 330, 350, or the paths 370, 380, 390. Of course, all the other paths of three symbol duration are also examined to determine the likelihood that the detected bit sequence followed these possible paths, but for the sake of simplicity of illustration, only the paths from state 0 to state 0 are considered here.
In order to identify the most likely path, the decoder determines the probability that the detected data sequence was produced by the first path (e.g., the path 310, 330, 350), the probability that the detected data sequence was generated by the second path (e.g., the path 370, 380, 390), and so on until a probability has been calculated for each possible path. The path having the highest probability is then selected as the actual path according to either hard or soft decision methods described in greater detail below.
Typically, trellis decoding techniques calculate path probabilities based upon either Hamming or Euclidean distances between the detected signal and the signals generated by the possible trellis paths. In accordance with the teachings of the present invention, Euclidean distances are used as the measure of path probability, as discussed in greater detail below. However, in order to provide a clearer understanding of the method of determining the probability of a possible trellis path, a brief discussion of Hamming distance is also provided.
Hamming distance is defined as the number of bits by which two binary sequences differ. For example, the hamming distance between the binary words 110 and 101 is two, while the hamming distance between the binary words 111 and 011 is one, etc. Based upon a Hamming distance evaluation of the possible paths, the probability that a given path has generated a detected data sequence can be determined s follows. Assuming, as stated above, that the detected data sequence is 11-11-11 (with a proper data sequence 11-10-11), and the possible paths are the paths 310, 330, 350 and 370, 380, 390, the Hamming distance between the detected signal 11-11-11 and the path 310, 330, 350 is 1. That is, because the path 310 generates an output of 3(11), and path 330 generates an output of 2(10), and the path 350 generates an output of 3(11), the binary sequence generated by the path 310, 330, 350 is 11-10-11. This sequence differs from the detected sequence 11-11-11 by a Hamming distance of 1. The Hamming distance between the detected signal 11-11-11 and the signal generated by the path 370, 380, 390 is 6 since the path 370, 380, 390 results in an output binary sequence of 00-00-00. Thus, it is much more likely that the detected sequence 11-11-11 was generated by the path 310, 330, 350, than by the path 370, 380, 390. Therefore, it is more likely that the sequence of input bits is 1-0-0.
Another measure of the probability that a given path has generated a binary sequence is based upon Euclidean distance. Euclidean distance is the length of a straight line between points on a signal constellation. In general, probability measures based upon Euclidean distances exhibit better accuracy than probability measures based on Hamming distance. This is because probability measurements based upon Euclidean distance take into account the received signal phase and amplitude information which is discarded when using Hamming distance as a probability metric.
For example, FIGS. 3A-3D illustrate a simple 4-PSK modulation signal constellation having four defined points 400, 410, 420, 430 equidistant from the origin and corresponding to output values, 00, 01, 10, and 11, respectively. Suppose a sequence of received data symbols are detected to have phase and amplitude values which are represented by the vectors r1-r3 in FIGS. 3A-3C. Using conventional Hamming decoding techniques, the vectors r1-r3 would simply be approximated as the data points, 00, 10, and 00, respectively, so that valuable phase and amplitude information is lost about the actually detected signal sequence. In accordance with Euclidean techniques, however, the phase and amplitude of the received signal are factored into the determination of the path probability.
As shown in FIG. 3D, the probability that the detected signal has been generated by the trellis path represented by the dashed line 450 is a decreasing function of the sum of the square of the Euclidean distances d01, d02, and d03 (depicted in FIGS. 3A-3C), while the probability that the detected signal has been generated by the trellis path represented by the dashed/dotted line 470 is a function of the sum of the squares of the Euclidean distances d31, d22, and d33. The greater the sum of the squares of the Euclidian distances along a given path, the less likely that path is to be the one which generated the detected signal sequence. In this manner, a more accurate estimation of the transmitted data sequence can be obtained.
It should be understood, of course, that as the number of points in the signal constellation (i.e., the number of possible output values) and the number of states in the trellis encoder increase, the number of possible trellis paths increases as well. Thus, for example, a rate xc2xe trellis encoder which operates in conjunction with a 16 point constellation will have 8 possible branches merging into and diverging out of each state (represented by a point) on the trellis state transition diagram. In these systems, the probability associated with each path merging into a state point is determined. Once these probabilities have been compared, the path with the highest probability is determined and corresponding data bits in that path are selected as the decoded sequences.
The selection of a given path may be made in accordance with block or symbol-by-symbol decision methods. In the case of a block decision, a predetermined number of received signals forming a set (e.g., 1,000 symbols) are fed into the decoder. The decoder then starts with the first signal and constructs a trellis with associated metrics and path histories for the whole set of 1,000 symbols. The trellis transition path that is most probable is then selected as the path which generated the detected symbols. The data input which would have generated this path is then determined as the decoded data sequence. Absent any uncorrected errors, this data sequence should correspond to the data sequence fed into the encoder on the transmitter side of the communication system. The process is then repeated with the next block of symbols, and so on.
For symbol-by-symbol decisions, a predetermined number of received signals are fed into the decoder. For example, assume 25 signals are fed into the decoder. Once the 25th symbol is entered, the trellis decoder determines what path was most probable. The input symbol which would have generated the first branch of the most probable path is then selected as the output of the decoder. The next (e.g., the 26th) received signal is then fed into the decoder and another determination is made of the most probable path for the last 25 symbols (i.e., excluding the first symbol). The input symbol which would have generated the first branch of the most probable path (i.e., the path for the most recently detected 25 symbols) is then selected as the next output of the decoder. This procedure is carried on symbol-by-symbol in real time so that only one symbol at a time is decoded for output as opposed to an entire block of data at a time.
Gottfried Ungerboeck, in a paper entitled xe2x80x9cChannel Coding with Multilevel/Phase Signals,xe2x80x9d published January, 1982 in IEEE Trans. Info. Thy., Vol. IT-28, No. 1, and herein incorporated by reference, argued that error performance of convolutional codes could be improved if designed by maximizing the Euclidean distances between trellis paths which merge into and out of the same state. This is accomplished by tailoring the convolutional coding scheme to the signal constellation of a given modulation technique so that the operations of error coding and modulation are essentially combined.
Take as a simple example a 4-PSK signal constellation as shown in FIG. 4. The possible outputs of the trellis encoder on the transmitter side are presented as four points which are phase shifted from one another by phase differences of 90xc2x0. In any trellis coding scheme the possible output values, as represented in the signal constellation, as well as the states of the trellis decoder are both considered. In order to provide the maximum distinction between encoded signals, so as to allow for more accurate decoding, it is advantageous to assure that transitions to and from the same state differ greatly in their output values (in terms of their Euclidean distances). For example, the trellis diagram of FIG. 2, which may, for example, describe state transitions for the 4-PSK signal constellation of FIG. 4, has the branches 370, 310 diverging from the same state point 300. Note that the output value for the state transition branch 310 is 3, and the output value for the state transition branch 370 is 0. In accordance with the Ungerboeck teaching, these two output values differ by the maximum Euclidean distance (i.e., a Euclidean distance of xcex94=2 as represented in FIG. 4). In a similar way, state transitions resulting in the same output values are assigned as transitions between two different states. Note, for instance, that the transition path 310 which results in an output value of 3 advances from state 00 to state 10, while a transition path 395 which also results in an output value of 3, advances from state 01 to state 00. The Ungerboeck method thus assures good discrimination between the encoded data signals.
The most common method of trellis encoding in accordance with Ungerboeck""s teachings is set partitioning, of which a simple example is shown in FIG. 4. By partitioning the original 4-PSK signal into two sets of diametrically opposed 2-PSK signals based upon the state of the trellis encoder, the maximum Euclidean distance can be maintained between outputs merging into or diverging out of the same state. Such set partitioning diagrams are commonly referred to as trellis coding trees.
The present invention provides a method of encoding a plural-bit data word as a plurality of multi-level symbols, each having a value selected from a predetermined plurality of levels, comprising the steps of a first translation of each of selected bit positions of the data word to one of the levels, when the contents of a predetermined one of the data word bits is a predetermined value, a second translation of each of the selected data word bit positions to one of the levels, generating a plural-bit offset word from predetermined bit positions of the data word and generating the multi-level symbols by addition of the offset word to the translated levels.
In a further aspect of the encoding method provided by the invention the multi-level symbols are assigned a five-level code, comprising a first, a second, a third, a fourth and a fifth code level, and wherein the first translation step further includes the step of translating a first predetermined bit value to the third code level and a second predetermined bit value to the second code level. Further to the encoding method wherein the data-word comprises the bits Sd[8:0], the offset-word comprises the bits V0, V1, V2 and V3 and the offset-word generating step further includes the step when the contents of said predetermined one of the data word bits is the predetermined value, generating the bits V0, V1, V2 and V3 according to the equations:
V0=Sd[4]
V1=Sd[4]{circumflex over ( )}Sd[6]
V2=Sd[4]{circumflex over ( )}Sd[6]{circumflex over ( )}Sd[7]
V3=Sd[4]{circumflex over ( )}Sd[7]{circumflex over ( )}Sd[8],
where {circumflex over ( )} is the XOR operation.
The encoding method further provides wherein the data-word comprises the bits Sd[8:0], the offset-word comprises the bits V0, V1, V2 and V3 and the offset-word generating step further includes the step when the contents of said predetermined one of the data word bits is the predetermined value, generating the bits V0, V1, V2 and V3 according to the equations:
xe2x80x83V0=I4
V1=I4{circumflex over ( )}Sd[6]
V2=I4{circumflex over ( )}Sd[6]{circumflex over ( )}Sd[7]
V3=I4{circumflex over ( )}Sd[7]{circumflex over ( )}Sd[8],
where I4 is assigned a binary value according to the table:
where {circumflex over ( )} is the XOR operation.
In yet another aspect of the encoding method of the instant invention each of the multilevel symbols is encoded on a predetermined one of four signal lines and wherein the second translation step further includes the steps, when the contents of said predetermined one of the data word bits is said predetermined value, adding the fifth code value to one of the signal lines as selected by predetermined bit positions of the data word, discarding the symbol on the fourth signal line; and selecting the symbols on the remaining three signal lines from the symbols on the lines to which no fifth code value is added.
The encoding method according to the invention further provides that wherein the code levels are treated as twos-complement numbers, wherein each of the multi-level symbols is encoded on a predetermined one of four signal lines and wherein the offset-word addition step includes the step twos-complement addition of the offset-word bits to the code-levels on respective ones of the signal lines. And further that wherein the code levels are treated as twos-complement numbers, wherein each multi-level symbols is encoded on a predetermined one of four signal lines and wherein the offset-word addition step includes the step, when the contents of said predetermined one of the data word bits is the predetermined value, twos-complement addition of the offset-word bits to said code-levels on respective ones of the signal lines symbols on the three signal lines to which no fifth code value is added.
Also provided by the invention is a method of decoding a plurality of multi-level symbols as a plural-bit data word, each symbol having a value selected from a five-level code, each code level treated as a twos-complement number, comprising the steps of; a translation of each of selected bit positions of the twos-complement representation to predetermined bit positions of the data word, when the contents of a predetermined bit positions of a twos-complement representation of one of the symbol is a predetermined value, setting of predetermined bit positions of the data word to a selected value; generating a plural-bit offset word from predetermined bit positions of the twos-complement representation of each of the symbols; and generating predetermined bit positions of the data-word from the offset word to a selected value, dependent on the contents of the predetermined bit positions of a twos-complement representation of one of the symbol being the predetermined value.
The decoding method of the invention further provides that wherein the five-level code comprises a first, a second, a third, a fourth and a fifth code level, wherein the contents of a predetermined bit positions of a twos-complement representation of one of said symbol is the fifth level, wherein each multi-level symbols is encoded on a predetermined one of four signal lines, wherein the twos-complement representation of the four multi-level symbols comprises the bits A[2:0], B[2:0], C[2:0] and D[2:0], the data-word comprises the bits Sd[8:0], and wherein the translation step further includes the steps:
A[2]=Sd[0]
B[2]=Sd[1]
C[2]=Sd[2]
D[2]=Sd[3].
In another aspect of the decoding method wherein the offset-word comprises the bits V0, V1, V2 and V3 and the offset-word generating step further includes the steps:
V0=A[0]
V1=B[0]
V2=C[0]
V3=D[0].
The decoding method of the invention also calls for when the step of setting of predetermined bit positions of the data word to a selected value further includes the steps:
Sd[6]=V0{circumflex over ( )}V1
Sd[7]=V1{circumflex over ( )}V2
Sd[8]=V0{circumflex over ( )}V1{circumflex over ( )}V2{circumflex over ( )}V3, where {circumflex over ( )} is the XOR operation. And the decoding method provided by the invention wherein when the contents of the predetermined bit positions of the twos-complement represents the fifth code level, the step of setting of predetermined bit positions of the data word to a selected value further includes the steps;
Sd[4]=V0
Sd[5]=0.
The decoding method in yet another aspect of the invention provides that wherein when the contents of the predetermined bit positions of the twos-complement represents the fifth code level, the step of setting of predetermined bit positions of the data word to a selected value further includes the steps: Sd[5:3]=100, if A[2:0]=the fifth code level, Sd[5:3]=110, if B[2:0]=the fifth code level, Sd[5:3]=101, if C[2:0]=the fifth code level, Sd[5:3]=111, if D[2:0]=the fifth code level; and Sd[0:2] is selected from compacted bits of Sd[0:3], dependent on which of the A[2:0], B[2:0], C[2:0], D[2:0]=the fifth code level.